/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-03-14
 * Time: 22:35
 */
public class TestDemo {

//    /**
//     * Definition for singly-linked list.
//     * class ListNode {
//     *     int val;
//     *     ListNode next;
//     *     ListNode(int x) {
//     *         val = x;
//     *         next = null;
//     *     }
//     * }
//     */
//    public class Solution {
//        public boolean hasCycle(ListNode head) {
//            ListNode fast =head;
//            ListNode slow =head;
//            while(fast!=null&&fast.next!=null) {
//                fast=fast.next.next;
//                slow=slow.next;
//                if(slow==fast) {
//                    return true;
//                }
//            }
//            return false;
//        }
//    }
//
//
//    /**
//     * Definition for singly-linked list.
//     * public class ListNode {
//     *     int val;
//     *     ListNode next;
//     *     ListNode() {}
//     *     ListNode(int val) { this.val = val; }
//     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//     * }
//     */
//    class Solution {
//        public boolean isPalindrome(ListNode head) {
//            if(head==null) {
//                return false;
//            }
//            if(head.next==null) {
//                return true;
//            }
//            //先找到链表的中间结点
//            ListNode fast =head;
//            ListNode slow =head;
//            while(fast!=null&&fast.next!=null) {
//                fast=fast.next.next;
//                slow =slow.next;
//            }
//            //此时中间结点是slow
//            ListNode cur =slow.next;
//            while(cur!=null) {
//                ListNode curNext =cur.next;
//                cur.next=slow;
//                slow= cur;
//                cur =curNext;
//            }
//            //此时我们进行一个指针往后走一个指针往前走
//            while(slow!=head) {
//                if(head.val!=slow.val) {
//                    return false;
//                }
//                if(head.next==slow) {
//                    return true;
//                }
//                slow=slow.next;
//                head=head.next;
//            }
//            return true;
//        }
//    }
//
//    /**
//     * Definition for singly-linked list.
//     * public class ListNode {
//     *     int val;
//     *     ListNode next;
//     *     ListNode() {}
//     *     ListNode(int val) { this.val = val; }
//     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//     * }
//     */
//    class Solution {
//        public ListNode deleteDuplicates(ListNode head) {
//            ListNode newHead =new ListNode(0,head);
//            ListNode cur = head;
//            ListNode tmp = newHead;
//            while(cur!=null) {
//                if(cur.next!=null&&cur.val==cur.next.val) {
//                    while(cur.next!=null&&cur.val==cur.next.val) {
//                        cur=cur.next;
//                    }
//                    // cur=cur.next;
//                }else {
//                    tmp.next=cur;
//                    tmp=tmp.next;
//                    cur=cur.next;
//                }
//            }
//            tmp.next=null;
//            return newHead.next;
//
//        }
//    }
//
//
//    /**
//     * Definition for singly-linked list.
//     * public class ListNode {
//     *     int val;
//     *     ListNode next;
//     *     ListNode() {}
//     *     ListNode(int val) { this.val = val; }
//     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//     * }
//     */
//    class Solution {
//        public ListNode deleteDuplicates(ListNode head) {
//            ListNode newHead =new ListNode(0,head);
//            ListNode cur = head;
//            ListNode tmp = newHead;
//            while(cur!=null) {
//                if(cur.next!=null&&cur.val==cur.next.val) {
//                    while(cur.next!=null&&cur.val==cur.next.val) {
//                        cur=cur.next;
//                    }
//                    cur=cur.next;
//                }else {
//                    tmp.next=cur;
//                    tmp=tmp.next;
//                    cur=cur.next;
//                }
//            }
//            tmp.next=null;
//            return newHead.next;
//
//        }
//    }
//
//
//    /**
//     * Definition for singly-linked list.
//     * public class ListNode {
//     *     int val;
//     *     ListNode next;
//     *     ListNode() {}
//     *     ListNode(int val) { this.val = val; }
//     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//     * }
//     */
//    class Solution {
//        public ListNode partition(ListNode head, int x) {
//            ListNode bs = null;
//            ListNode be = null;
//            ListNode as = null;
//            ListNode ae = null;
//            ListNode cur =head;
//            while(cur!=null) {
//                if(cur.val<x) {
//                    //第一次插入
//                    if(bs==null) {
//                        bs=cur;
//                        be=cur;
//                    }else {
//                        be.next =cur;
//                        be =be.next;
//                    }
//                }else {
//                    if(as==null) {
//                        as=cur;
//                        ae=cur;
//                    }else {
//                        ae.next =cur;
//                        ae = ae.next;
//                    }
//                }
//                cur=cur.next;
//            }
//            if(bs==null) {
//                return as;
//            }
//            else {
//                be.next=as;
//                if(as!=null) {
//                    ae.next=null;
//                }
//            }
//            return bs;
//        }
//    }
      class ListNode {
          int val;
          ListNode next;
          ListNode(int x) {
              val = x;
             next = null;
         }
      }

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=null&&fast.next!=null) {
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow) {
                    while(head!=slow) {
                        head=head.next;
                        slow=slow.next;
                    }
                    return slow;
                }
            }
            return null;

        }
    }

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            //计算两个链表的差值
            int lenA =0;
            int lenB =0;
            ListNode curA =headA;
            ListNode curB =headB;
            while(curA!=null) {
                lenA++;
                curA=curA.next;
            }
            while(curB!=null) {
                lenB++;
                curB=curB.next;
            }
            ListNode pl = headA;//长的
            ListNode ps = headB;//短的
            int gap =lenA-lenB;;//两个链表之间相差的长度
            if(lenA<lenB) {
                pl=headB;
                ps=headA;
                gap =lenB-lenA;
            }
            while(gap!=0) {
                pl=pl.next;
                gap--;
            }
            //此时两个(pl和ps)同时走一直到相遇
            while(pl!=ps&&pl!=null&&ps!=null) {
                pl=pl.next;
                ps=ps.next;
            }
            //此时pl与ps相遇
            if(pl==ps&&pl!=null&&ps!=null) {
                return ps;
            }
            return null;
        }
    }



}
